package com.sam.questionBank;


import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/combinations/description/
 *
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * 输入: n = 3, k = 2
 输出:[[2, 3], [1, 3], [1, 2]]
 * Created by samwang on 2018/4/7.
 */
public class Combine1toNKlength {

    public static void main(String[] args) {
        Combine1toNKlength temp = new Combine1toNKlength();
        System.out.println(temp.combine(3, 2));

    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>(k);
        combine(n,k,1,temp,result);

        return result;

    }

    private void combine(int n, int k, int start, List<Integer> data, List<List<Integer>> result) {
        if(data.size() == k){
            result.add(data);
        }else if(start <= n) {
            if (k - data.size() > n - start + 1) {
                return;
            }

            List<Integer> list = new ArrayList<>(data.size());
            if (!data.isEmpty()) {
                list.addAll(data);
            }
            combine(n, k, start + 1, list, result);
            data.add(start);
            combine(n, k, start + 1, data, result);
        }
    }
}
